ABC275 D - Yet Another Recursive Function

提出

TLE

code: python

import math

n = int(input())

# f(0)が何個できるか

def f(n):

if n == 0:

return 1

else:

return f(math.floor(n/2)) + f(math.floor(n/3))

ans = f(n)

print(ans)

解答

code: python

n = int(input())

memo = {}

def f(i):

if i == 0:

return 1

if i not in memo:

memoi = f(i // 2) + f(i // 3)

return memoi

print(f(n))

テーマ

メモ

提出

code: python

import math

n = int(input())

# f(5) = f(5/2) + f(5/3) = f(2) + f(1) = (f(2/2) + f(2/3)) + (f(1/2) + f(1/3)) = f(1) + f(0) + f(0) + f(0) = 5

# dpi := f(i) の値

# dp = 0 * pow(10, 18)

dp = 0 * pow(10, 10)

dp0 = 1

for i in range(1, 100):

print(dp)